/*
题目: 等差数列划分
如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。

    例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。

给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。

子数组 是数组中的一个连续序列

https://leetcode.cn/problems/arithmetic-slices
 */
public class NumberOfArithmeticSlices {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        if (n < 3)  return 0;

        // 表示 从 dp[i] 处开始到这里 都是等差数列
        // dp[i] 记录的是等差数列的头部下标
        // 那么等差数列的长度就是 i - dp[i] + 1
        int[] dp = new int[n];
        Arrays.fill(dp, -1);
        dp[0] = dp[1] = 0; // 从 0 下标到这里都是等差数列

        int src = 0;
        for (int i = 2; i < n; i ++) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                if (dp[i - 1] == -1) { // 前面那一坨不是等差数列
                    dp[i] = i - 2;     // 不是的话, 现在就记录头部下标
                } else { // 是等差数列
                    dp[i] = dp[i - 1];  // 继承头部下标
                }

                // 长度小于 3 就不加了, 否则答案 += 长度 - 2 (下式化简了)
                src += i - dp[i] >= 2 ? i - dp[i] - 1 : 0;
            }
        }

        return src;
    }
}
